#include "SeqList.h"

void SeqListInit(SL* ps)
{
	ps->_a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->_a == NULL)
	{
		exit(-1);
	}
	ps->size = 0;
	ps->capicity = 4;
}

void SeqListDestory(SL* ps)
{
	free(ps->_a);
	ps->_a = NULL;
	ps->size = 0;
	ps->capicity = 0;
}


void SeqListCheckCapicity(SL* ps)
{
	if (ps->size >= ps->capicity)
	{
		
		ps->capicity *= 2;
		ps->_a = (SLDataType*)realloc(ps->_a, sizeof(SLDataType)*ps->capicity);
		if (ps->_a == NULL)
		{
			exit(-1);
		}
	}
}


void SeqListPushBack(SL* ps, SLDataType	x)
{
	SeqListCheckCapicity(ps);

	ps->_a[ps->size] = x;
	ps->size++;
}

void SeqListPrintf(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->_a[i]);
		
	}
	printf("\n");
}	

void SeqListPopBack(SL* ps)
{
	//ps->_a[ps->size - 1] = 0;
	
	ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapicity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->_a[end + 1] = ps->_a[end];
		--end;
	}

	SeqListCheckCapicity(ps);
	ps->_a[0] = x;
	ps->size++;

}
//ͷɾ
void SeqListPopFront(SL* ps)
{
	assert(ps);
	int start = 0;
	while (start < ps->size - 1)
	{
		ps->_a[start] = ps->_a[start + 1];
		++start;
	}
	ps->size--;
}

void SqeListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);

	assert(pos < ps->size&&pos>=0);
	SeqListCheckCapicity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->_a[end + 1] = ps->_a[end];
		--end;
	}
	SeqListCheckCapicity(ps);
	ps->_a[pos] = x;
	ps->size++;

}



void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	int start = pos ;
	while (start < ps->size - 1)
	{
		ps->_a[start] = ps->_a[start + 1];
		start++;
	}
	ps->size--;

}

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;

	for ( i = 0; i < ps->size;i++)
	{
		if (ps->_a[i] == x)
		{
			return i;
		}
	}
	if (i == ps->size)
	{
		printf("zd\n");
	}
}

int Swap(const void* e1, const void* e2)
{
	return *((SLDataType*)e1) - *((SLDataType*)e2);
}



void SeqListSort(SL* ps)
{
	assert(ps);
	qsort(ps->_a, ps->size, sizeof(SLDataType), Swap);

}

int SeqListBinaryFind(SL* ps, SLDataType x)
{
	assert(ps);
	qsort(ps->_a, ps->size, sizeof(SLDataType), Swap);
	int start = 0;
	int end = ps->size - 1;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (x > ps->_a[mid])
		{
			start = mid;
		}
		else if (x < ps->_a[mid])
		{
			end = mid;
		}
		else
		{
			return mid;
		}
	}
	return -1;
	
}